// https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
// Created by ade on 2022/7/25.
//
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode * node = nullptr;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return node;
    }

    void dfs(TreeNode* root, TreeNode* p, TreeNode* q){
        if(root){
            if (root->val == p->val
                || root->val == q->val
                || root->val > p->val && root->val < q->val
                || root->val < p->val && root->val > q->val
                    ){
                node = root;
                return;
            }
            dfs(root->left, p, q);
            dfs(root->right, p, q);
        }
    }
};

int main() {
    Solution so;
    TreeNode *h1 = so.init();
    auto res = so.levelOrder(h1);
    for (auto items : res) {
        for (auto i : items) {
            cout << i << ",";
        }
        cout << endl;
    }
    return 0;
}